Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public List<Integer> preorderTraversal(TreeNode root) {
  12.     List<Integer> res = new ArrayList<Integer>();
  14.     if (root == null)
  15.       return res;
  17.     Stack<TreeNode> stack = new Stack<TreeNode>();
  18.     stack.push(root);
  20.     while (!stack.isEmpty()) {
  21.       TreeNode node = stack.pop();
  22.       res.add(node.val);
  24.       if (node.right != null)
  25.         stack.push(node.right);
  27.       if (node.left != null)
  28.         stack.push(node.left);
  29.     }
  31.     return res;
  32.   }
  33. }